//	ID : pallab81
// 	PROG : 164again
// 	LANG : C++
// 	2011-08-02-21.52.52 Tuesday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define fo(i,ed) for(int i = 0 ; i < ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

string source, sink;
int len1,len2;
int rem[ 30 ][ 30 ];

inline int go(int i, int j) {
    if( i==len1 && j==len2 ) {
        return 0;
    }
    int &best = rem[ i ][ j ];
    if( best!=-1 ) {
        return best;
    }

    best = (int)1023456789;

    if( i==len1 && j < len2 ) {
        best = 1+go(i,j+1); // insert a char
    } else if( i < len1 && j==len2 ) {
        best = 1+go(i+1,j); // delete a char
    } else {
        if( source[i]==sink[j] ) {
            best = min(best, go(i+1,j+1) );
        } else {
            best = min(best, 1+go(i+1,j+1));
        }
        int var1 = 1+go(i+1,j); // delete a char
        int var2 = 1+go(i,j+1); // insert a char
        best = min( best, min(var1,var2 ) );
    }
    return best;
}
inline void back_track(int i, int j, int index) {
    if( i==len1 && j==len2 ) {
        return ;
    }
    if( i==len1 && j<len2 ) {
        printf("I%c%02d",sink[j],index);
        back_track(i,j+1,index+1); //insert a char
    } else if( i<len1 && j==len2 ) {
        printf("D%c%02d",source[i],index);
        back_track(i+1,j, index); //delete a char
    } else {
        int var0 = (int)1023456789;
        if( source[i]==sink[j] ) {
            var0 = go(i+1,j+1);
        } else {
            var0 = 1+go(i+1,j+1);
        }
        int var1 = 1+go(i+1,j); // delete a char
        int var2 = 1+go(i,j+1); // insert a char

        if( var0 <= min(var1, var2) ) {
            if(source[i]==sink[j]) {
                back_track(i+1,j+1,index+1);
            } else {
                printf("C%c%02d",sink[j],index);
                back_track(i+1,j+1,index+1);
            }
        } else if( var1 <= min(var0 , var2) ) {
            printf("D%c%02d",source[i],index);
            back_track(i+1,j, index);   // delete a char
        } else {
            printf("I%c%02d",sink[j],index);
            back_track(i,j+1,index+1); //insert a char
        }

    }
}
inline void proc() {
    SET(rem,-1);
    len1 = LN(source);
    len2 = LN(sink);
    go(0,0);
    back_track(0,0,1);
    printf("E\n");
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt","rt",stdin);
#endif

    while(cin>>source && source !="#" ) {
        cin>>sink;
        proc();
    }
    return 0;
}


